package leetcode.algorithm.linkedlist.simple.tree;


import java.util.LinkedList;
import java.util.Queue;

import leetcode.algorithm.TreeNode;

/**
 * 合并二叉树
 *
 * @author jiangwz
 * @create 2019/11/7.
 */
public class Q617 {

    public static void main(String[] args){

    }


    /**
     * 执行用时 :
     * 1 ms
     * , 在所有 java 提交中击败了
     * 99.27%
     * 的用户
     * 内存消耗 :
     * 39.7 MB
     * , 在所有 java 提交中击败了
     * 96.01%
     * 的用户
     * @param t1
     * @param t2
     * @return
     */
//    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
//        if (t1 == null)
//            return t2;
//        if (t2 == null)
//            return t1;
//        t1.val += t2.val;
//        t1.left = mergeTrees(t1.left, t2.left);
//        t1.right = mergeTrees(t1.right, t2.right);
//        return t1;
//    }

    /**
     * 执行用时 :
     * 2 ms
     * , 在所有 java 提交中击败了
     * 47.71%
     * 的用户
     * 内存消耗 :
     * 43.8 MB
     * , 在所有 java 提交中击败了
     * 83.73%
     * 的用户
     * @param t1
     * @param t2
     * @return
     */
    // 递归方式(留待实现)
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        if (t1 == null)
            return t2;
        if (t2 == null)
            return t1;
        Queue<TreeNode[]> queue = new LinkedList<>();
        queue.add(new TreeNode[]{t1, t2});
        while (!queue.isEmpty()) {
            TreeNode[] t = queue.poll();
            if (t[0] == null || t[1] == null)
                continue;
            t[0].val += t[1].val;
            if (t[0].left == null){
                t[0].left = t[1].left;
            }else {
                queue.add(new TreeNode[]{t[0].left, t[1].left});
            }
            if (t[0].right == null) {
                t[0].right = t[1].right;
            }else {
                queue.add(new TreeNode[]{t[0].right, t[1].right});
            }
        }
        return t1;
    }


}
